package com.zk.algorithm.tree;

import com.zk.algorithm.annotation.Finished;
import com.zk.algorithm.annotation.LeetCode;
import com.zk.algorithm.bean.TreeNode;

/**
 * 前序和后序构建树，并不能唯一确定一颗二叉树
 *
 * pre = [1,2,4,5,3,6,7]
 * post = [4,5,2,6,7,3,1]
 *
 * 不唯一的举例:
 *     2
 *    /
 *   1
 *  /
 * 3
 *
 * 前序: 2, 1, 3 后序: 3, 1, 2
 *
 * 2
 *  \
 *   1
 *    \
 *     3
 *
 * 前序: 2, 1, 3 后序 3, 1, 2
 *
 * @author zk
 */
@LeetCode
@Finished(false)
public class ConstructTreeWithPreAndPostOrder {

    public TreeNode buildTree(int[] preOrder, int[] postOrder) {
        return helper(
                preOrder, 0, preOrder.length - 1,
                postOrder, 0, postOrder.length - 1
        );
    }

    /**
     * [1,2,4,5,3,6,7]
     * [4,5,2,6,7,3,1]
     *
     * [2,4,5,3,6,7]
     * [4,5,2,6,7,3]
     *
     * [2,(4,5),(3,6,7)]
     * [(4,5),2,(6,7,3)]
     *
     * [4,5]
     * [4,5]
     *
     * @param preOrder
     * @param preStart
     * @param preEnd
     * @param postOrder
     * @param postStart
     * @param postEnd
     * @return
     */
    private TreeNode helper(int[] preOrder, int preStart, int preEnd,
                            int[] postOrder, int postStart, int postEnd) {
        if (preStart > preEnd || postStart > postEnd) {
            return null;
        }

        int rootVal = preOrder[preStart];
        TreeNode root = new TreeNode(rootVal);

        boolean last = isRootLastInPostOrder(rootVal, postOrder, postEnd);
        if (last) {
            root.left = helper(preOrder, preStart + 1, preEnd,
                    postOrder, postStart, postEnd - 1);
        } else {
            int rootIndex = findRootIndexInPostOrder(rootVal, postOrder, postStart, postEnd);
            int leftInterval = rootIndex - postStart + 1;

            root.left = helper(preOrder, preStart + 1, preStart + leftInterval,
                    postOrder, postStart, rootIndex - 1);
            root.right = helper(preOrder, preStart + leftInterval, preEnd,
                    postOrder, rootIndex + 1, postEnd);
        }

        return root;
    }

    private boolean isRootLastInPostOrder(int rootVal, int[] postOrder, int postEnd) {
        return postOrder[postEnd] == rootVal;
    }

    private int findRootIndexInPostOrder(int rootVal, int[] postOrder, int postStart, int postEnd) {
        for (int i=postStart; i<=postEnd; i++) {
            if (rootVal == postOrder[i]) {
                return i;
            }
        }

        return -1;
    }

}
